/*	Program P12-6 Depth-first traversal.
	
    Brooks/Cole Publishing Company
	An International Thomson Publishing Company
	Copyright 1998. All Rights Reserved
*/

/*	==================== depthFirst ====================
	Process the data in the graph in depth-first order.
	   Pre      nothing
	   Post     vertices "processed"
*/

template <class TYPE, class KTYPE> 
void Graph<TYPE, KTYPE> :: depthFirst 
          (void (*process)(TYPE dataProc))
{
 // Local Definitions 
	bool                  success;
	Vertex<TYPE>         *walkPtr;
	Vertex<TYPE>         *vertexPtr;
	Vertex<TYPE>         *vertToPtr;
	Stack<Vertex<TYPE>*>  stack;
	Arc<TYPE>            *arcWalkPtr;
	
//	Statements 
	if (!first)
	    return;

	//  Set processed flags to not processed 
	walkPtr = first;
	while (walkPtr)
	   {
	    walkPtr->processed = 0;
	    walkPtr            = walkPtr->pNextVertex;
	   } // while 
	
	// Process each vertex in list 
	walkPtr = first;
	while (walkPtr)
	   {
	    if (walkPtr->processed < 2)
	       {
	        if (walkPtr->processed < 1)
	           {
	            // Push and set flag to pushed 
	            success = stack.pushStack (walkPtr);
	            if (!success)
	               cout << "\aStack overflow 100\a\n",
	                  exit (100); 	            
	            walkPtr->processed = 1;
	           } // if processed < 1 
	       } // if processed < 2
	    // Process descendents of vertex at stack top 
	    while (!stack.emptyStack ())
	       {
	        stack.popStack(vertexPtr);
	        process (vertexPtr->data);
	        vertexPtr->processed = 2;
	        
	        // Push all vertices from adjacency list 
	        arcWalkPtr = vertexPtr->pArc;
	        while (arcWalkPtr)
	           {
	            vertToPtr = arcWalkPtr->destination;
	            if (vertToPtr->processed == 0)
	               {
	                success = stack.pushStack(vertToPtr);
	                if (!success)
	                 cout << "\aStack overflow 101\a\n",
	                    exit (101);
	                vertToPtr->processed = 1;
	               } // if vertToPtr 
	            arcWalkPtr = arcWalkPtr->pNextArc;
	           } // while arcWalkPtr 
	       } //  while !emptyStack 
	    walkPtr = walkPtr->pNextVertex;
	   } // while walkPtr 
	return;
} // depthFirst 
